package listbyorder.access201_300.test297;

import listbyorder.utils.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/28 16:08
 */
// 方法一； 按层进行序列化
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "#!";
        StringBuilder ans = new StringBuilder();
        ans.append(root.val + "!");
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            root = queue.poll();
            if (root.left != null) {
                ans.append(root.left.val + "!");
                queue.add(root.left);
            } else {
                ans.append("#!");
            }
            if (root.right != null) {
                ans.append(root.right.val + "!");
                queue.add(root.right);
            } else {
                ans.append("#!");
            }
        }
        return ans.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        // 将给定字符串划分成为字符数组
        String[] strings = data.split("!");
        Queue<TreeNode> queue = new LinkedList<>();
        int index = 0;
        TreeNode head = generateNode(strings[index++]);
        if (head != null) {
            queue.add(head);
        }
        TreeNode node = null;
        while (!queue.isEmpty()) {
            node = queue.poll();
            node.left = generateNode(strings[index++]);
            node.right = generateNode(strings[index++]);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        return head;
    }

    private TreeNode generateNode(String s) {
        if (s.equals("#")) {
            return null;
        } else {
            return new TreeNode(Integer.parseInt(s));
        }
    }
}
